package hash;

import java.util.*;

public class ConsistencyHash {
    // 真实节点列表
    private List<String> hosts = new ArrayList<>();
    // 真实节点-虚拟节点映射
    private Map<String, List<String>> vMap = new HashMap<>();
    // 每个真实节点需要创建多少个虚拟节点
    private final int vNum;
    // hash 环
    private TreeMap<Integer, String> hashCycle = new TreeMap<>();

    public ConsistencyHash(int vNum) {
        this.vNum = vNum;
    }

    /**
     * 添加一个节点
     * @param host
     */
    public void addHost(String host) {
        hosts.add(host);
        List<String> vList = new ArrayList<>(vNum);
        vMap.put(host, vList);

        int i = 0, count = 0;
        while(count < vNum) {
            String vk = String.format("%s$%d-vHost", host, i ++);
            int hash = HashUtil.FNVHash1(vk);
            if(!hashCycle.containsKey(hash)) {
                hashCycle.put(hash, host);
                vList.add(vk);
                count ++;
            }
        }
    }

    /**
     * 移除一个节点
     * @param host
     */
    public void remove(String host) {
        List<String> vList = vMap.get(host);
        if(vList != null)
            for (String s : vList) {
                hashCycle.remove(HashUtil.FNVHash1(s));
            }
        vMap.remove(host);
        hosts.remove(host);
    }

    /**
     * 获取key应该放到哪个host上
     * @param key
     * @return
     */
    public String getHost(String key) {
        if(hashCycle.isEmpty())
            return null;
        int hash = HashUtil.FNVHash1(key);
        SortedMap<Integer, String> tailMap = hashCycle.tailMap(hash);
        if(tailMap.isEmpty())
            return hashCycle.firstEntry().getValue();
        else
            return tailMap.get(tailMap.firstKey());
    }

    public static void main(String[] args) {
        ConsistencyHash consistencyHash = new ConsistencyHash(100);
        consistencyHash.addHost("192.168.0.1");
        consistencyHash.addHost("192.168.0.2");
        consistencyHash.addHost("192.168.0.3");

        System.out.printf("%s -> %s\n", consistencyHash.getHost("hello"), "hello");
        System.out.printf("%s -> %s\n", consistencyHash.getHost("guopanbo"), "guopanbo");
        System.out.printf("%s -> %s\n", consistencyHash.getHost("janna"), "janna");
        System.out.printf("%s -> %s\n", consistencyHash.getHost("123"), "123");
        System.out.printf("%s -> %s\n", consistencyHash.getHost("456"), "456");
        System.out.printf("%s -> %s\n", consistencyHash.getHost("tangyun"), "tangyun");
    }
}
